package main

import (
	"fmt"
	"sort"
)

//[7,3,2]
//18
func main() {
	candidates := []int{2,3,6,7}
	target := 7
	fmt.Print(combinationSum2(candidates, target))
}

func combinationSum(candidates []int, target int) [][]int {
	length := len(candidates)
	if length == 0 {
		return nil
		{
		}
	}
	sort.Ints(candidates)
	res := [][]int{}
	dfs1(candidates, 0, length, []int{}, &res, target)
	return res
}

func dfs1(candidates []int, begin int, size int, path []int, res *[][]int, target int) {
	if target == 0 {
		*res = append(*res, path)
		return
	}
	for index := begin; index < size; index++ {
		residue := target - candidates[index]
		if residue < 0 {
			break
		}

		temList := append(path, candidates[index])
		dfs1(candidates, index, size, temList, res, residue)
	}
}

func combinationSum1(candidates []int, target int) (ans [][]int) {
	comb := []int{}
	var dfs func(target, idx int)
	dfs = func(target, idx int) {
		if idx == len(candidates) {
			return
		}
		if target == 0 {
			ans = append(ans, append([]int(nil), comb...))
			return
		}
		// 直接跳过
		dfs(target, idx+1)
		// 选择当前数
		if target-candidates[idx] >= 0 {
			comb = append(comb, candidates[idx])
			dfs(target-candidates[idx], idx)
			comb = comb[:len(comb)-1]
		}
	}
	dfs(target, 0)
	return
}

func combinationSum12(candidates []int, target int) (ans [][]int) {
	sort.Ints(candidates)
	comb := []int{}
	var dfs func(target, idx int)
	dfs = func(target, idx int) {
		if target == 0 {
			ans = append(ans, append([]int(nil), comb...))
			return
		}

		for i := idx; i < len(candidates); i++ {
			residue := target - candidates[i]
			if residue < 0 {
				break
			}
			comb = append(comb, candidates[i])
			dfs(residue, i)
			comb = comb[:len(comb)-1]
		}
	}
	dfs(target, 0)
	return
}
